home *** CD-ROM | disk | FTP | other *** search
/ Gekkan Dennou Club 140 / Gekkan Dennou Club - 2000.1 Vol. 140 (Japan) (Track 1).bin / docs / perl / numpla / numplace.pl < prev   
Encoding:
Text File  |  1999-10-29  |  6.9 KB  |  328 lines
  1. #
  2. # numplace.pl : ナンバープレース自動解法
  3. #
  4. #               Copyright (C) 1999 by Makoto Hiroi
  5. #
  6.  
  7. # 外部変数定義
  8. @board = ();            # 盤面（２次元配列）
  9. @postion = ();          # 確定していない場所を格納
  10. @biton = ();
  11. @bitoff = ();
  12. @xflag = (0x3fe) x 9;
  13. @yflag = (0x3fe) x 9;
  14. @gflag = (
  15.   [0x3fe,0x3fe,0x3fe],
  16.   [0x3fe,0x3fe,0x3fe], 
  17.   [0x3fe,0x3fe,0x3fe]
  18. );
  19. @group   = (0,0,0,1,1,1,2,2,2);    # グループ
  20. @group_s = (0,0,0,3,3,3,6,6,6);    # スタート位置
  21.  
  22. # 初期化
  23. sub init_bit_table {
  24.   my $i;
  25.   for( $i = 1; $i <= 9; $i++ ){
  26.     $biton[$i] = 1 << $i;
  27.     $bitoff[$i] = 0x3fe - $biton[$i];
  28.   }
  29. }
  30.  
  31. # 解答の出力
  32. sub print_board {
  33.   foreach $a (@board) {
  34.     print "@$a\n";
  35.   }
  36.   print "\n";
  37. }
  38.  
  39. # 数字を書く
  40. sub write_number {
  41.   my ($n, $x, $y) = @_;
  42.   my $off = $bitoff[$n];
  43.   $board[$x][$y] = $n;
  44.   $xflag[$x] &= $off;
  45.   $yflag[$y] &= $off;
  46.   $gflag[ $group[$x] ][ $group[$y] ] &= $off;
  47. }
  48.  
  49. # 数字を消す
  50. sub delete_number {
  51.   my ($n, $x, $y) = @_;
  52.   my $on = $biton[$n];
  53.   $board[$x][$y] = 0;
  54.   $xflag[$x] |= $on;
  55.   $yflag[$y] |= $on;
  56.   $gflag[ $group[$x] ][ $group[$y] ] |= $on;
  57. }
  58.  
  59. # ビットを求める
  60. sub get_bit {
  61.   my ($x, $y) = @_;
  62.   $xflag[$x] & $yflag[$y] & $gflag[ $group[$x] ][ $group[$y] ];
  63. }
  64.  
  65. # ビットが一つで確定できるか
  66. sub kakutei_1 {
  67.   my $i;
  68.   for( $i = 0; $i < @postion; ){
  69.     my $x = $postion[$i++];
  70.     my $y = $postion[$i++];
  71.     my $f = &get_bit( $x, $y );
  72.     if( $f ){
  73.       my $n;
  74.       for( $n = 1; $n <= 9; $n++ ){
  75.         if( $f == $biton[$n] ){
  76.           &write_number( $n, $x, $y );
  77.         }
  78.       }
  79.     }
  80.   }
  81. }  
  82.  
  83. # 縦の確定
  84. sub kakutei_x {
  85.   my ($x,$y,$n);
  86.   for( $x = 0; $x < 9; $x++ ){
  87.     next if $xflag[$x] == 0;        # 全ての数字が埋まっている
  88.     for( $n = 1; $n <= 9; $n++ ){
  89.       my ($c,$p) = (0,0);
  90.       next unless ($xflag[$x] & $biton[$n]);
  91.       for( $y = 0; $y < 9; $y++ ){
  92.         if( $board[$x][$y] == 0 &&
  93.            (&get_bit( $x, $y ) & $biton[$n]) ){
  94.           $c++;
  95.           $p = $y;
  96.         }
  97.       }
  98.       &write_number( $n, $x, $p ) if $c == 1;
  99.     }
  100.   }
  101. }
  102.  
  103. # 横の確定
  104. sub kakutei_y {
  105.   my ($x,$y,$n);
  106.   for( $y = 0; $y < 9; $y++ ){
  107.     next if $yflag[$y] == 0;        # 全ての数字が埋まっている
  108.     for( $n = 1; $n <= 9; $n++ ){
  109.       my ($c,$p) = (0,0);
  110.       next unless ($yflag[$y] & $biton[$n]);
  111.       for( $x = 0; $x < 9; $x++ ){
  112.         if( $board[$x][$y] == 0 &&
  113.            (&get_bit( $x, $y ) & $biton[$n]) ){
  114.           $c++;
  115.           $p = $x;
  116.         }
  117.       }
  118.       &write_number( $n, $p, $y ) if $c == 1;
  119.     }
  120.   }
  121. }
  122.  
  123. # グループの確定
  124. sub kakutei_g {
  125.   my ($x,$y,$n);
  126.   for( $x = 0; $x < 9; $x += 3 ){
  127.     for( $y = 0; $y < 9; $y += 3 ){
  128.       next if $gflag[ $group[$x] ][ $group[$y] ] == 0;    # 全ての数字が埋まっているよ
  129.       for( $n = 1; $n <= 9; $n++ ){
  130.         next unless ($gflag[ $group[$x] ][ $group[$y] ] & $biton[$n]);
  131.         my ($c,$x1,$y1,$i,$j);
  132.         $c = 0;
  133.         for( $i = 0; $i < 3; $i++ ){
  134.           for( $j = 0; $j < 3; $j++ ){
  135.             if( $board[$x + $i][$y + $j] == 0 &&
  136.                (&get_bit($x + $i, $y + $j) & $biton[$n]) ){
  137.               $c++;
  138.               $x1 = $x + $i;
  139.               $y1 = $y + $j;
  140.             }
  141.           }
  142.         }
  143.         &write_number( $n, $x1, $y1 ) if $c == 1;
  144.       }
  145.     }
  146.   }
  147. }
  148.  
  149. # マスのある縦、横、枠をまとめてチェックする
  150. sub kakutei_search_1 {
  151.   while( 1 ){
  152.     # 確定１
  153.     &kakutei_1();
  154.     # 確定２
  155.     &kakutei_x();
  156.     &kakutei_y();
  157.     &kakutei_g();
  158.     # チェック
  159.     my ($i, $j);
  160.     for( $i = 0; $i < @postion; ){
  161.       my $x = $postion[$i++];
  162.       my $y = $postion[$i++];
  163.       if( $board[$x][$y] == 0 ){
  164.         $postion[$j++] = $x;
  165.         $postion[$j++] = $y;
  166.       }
  167.     }
  168.     if( $j == @postion ){
  169.       # 確定できなかった
  170.       return 0
  171.     } elsif( $j == 0 ){
  172.       # 確定したよ
  173.       return 1;
  174.     }
  175.     $#postion = $j - 1;
  176.   }
  177.   1;
  178. }
  179.  
  180. #
  181. # バックトラックによる解析
  182. # 再帰が深くなるとバスエラーが発生する
  183. #
  184. sub search {
  185.   my $pos = shift;
  186.   my ($x, $y, $f);
  187.   if( $pos == @postion ){
  188.     # 答えが見つかった
  189.     print_board();
  190.     return;
  191.   }
  192.   $x = $postion[$pos];
  193.   $y = $postion[$pos + 1];
  194.   $f = &get_bit( $x, $y );
  195.   if( $f ){
  196.     my $i;
  197.     for( $i = 1; $i <= 9; $i++ ){
  198.       if( $f & $biton[$i] ){
  199.         &write_number( $i, $x, $y );
  200.         &search( $pos + 2 );
  201.         &delete_number( $i, $x, $y );
  202.       }
  203.     }
  204.   }
  205. }
  206.  
  207. #
  208. # バックトラックを繰り返しに変換
  209. #
  210. sub search_1 {
  211.   my $pos = 0;
  212.   my @save_number = ();
  213.   my ($x, $y, $f, $i);
  214.   while( $pos >= 0 ){
  215.     if( $pos == @postion ){
  216.       # 答えが見つかった
  217.       print_board();
  218.       # 一つ見つけたら終了
  219.       return;
  220.     }
  221.     $x = $postion[$pos];
  222.     $y = $postion[$pos + 1];
  223.     if( $board[$x][$y] == 0 ){
  224.       # 新しい数値をセット
  225.       $i = 1;
  226.       $f = &get_bit( $x, $y );      
  227.     } else {
  228.       # 数字の選び直し
  229.       $i = $save_number[$pos];
  230.       $f = $save_number[$pos + 1];
  231.       &delete_number( $i, $x, $y );
  232.       $i++;
  233.     }
  234.     for( ; $i <= 9; $i++ ){
  235.       if( $f & $biton[$i] ){
  236.         # 数字をセット */
  237.         &write_number( $i, $x, $y );
  238.         # データセーブ
  239.         $save_number[$pos]     = $i;
  240.         $save_number[$pos + 1] = $f;
  241.         last;
  242.       }
  243.     }
  244.     if( $board[$x][$y] > 0 ){
  245.       # 数字をセットできたので次の位置へ
  246.       $pos += 2;
  247.     } else {
  248.       # 元に戻る
  249.       $pos -= 2;
  250.     }
  251.   }
  252. }
  253.  
  254. # データチェック
  255. sub data_check {
  256.   if( @postion == 0 ){
  257.     die "空いているマスがありません\n";
  258.   }
  259.   my $i = 0;
  260.   while( $i < @postion ){
  261.     my $x = $postion[$i++];
  262.     my $y = $postion[$i++];
  263.     unless( &get_bit( $x, $y ) ){
  264.       die "($x,$y) に数字を置くことができません\n";
  265.     }
  266.   }
  267. }
  268.  
  269. # 解析処理
  270. sub analysis {
  271.   my ($x, $y);
  272.   for( $x = 0; $x < 9; $x++ ){
  273.     for( $y = 0; $y < 9; $y++ ){
  274.       my $n = $board[$x][$y];
  275.       if( $n > 0 ){
  276.         if( &get_bit( $x, $y ) & $biton[$n] ){
  277.           &write_number( $n, $x, $y );
  278.         } else {
  279.           &print_board();
  280.           die "エラー：($x,$y) の数字 $n が矛盾している\n";
  281.         }
  282.       } else {
  283.         push( @postion, $x );
  284.         push( @postion, $y );
  285.       }
  286.     }
  287.   }
  288.   &data_check();
  289. }
  290.  
  291. # データリード
  292. sub read_data {
  293.   my $filename = shift;
  294.   open(IN,$filename) or die "ファイル $filename が見つかりません\n";
  295.   while( <IN> ){
  296.     # コメントと空行のチェック
  297.     next if( /^[;#]/ || /^\s*$/ );
  298.     my @item = split;
  299.     if( @item != 9 || grep( ($_ < 0 || $_ > 9), @item ) ){
  300.       die "エラーデータ : $_ １行に 0 - 9 の数字を 9 個並べてください\n";
  301.     }
  302.     push( @board, [ @item] );
  303.   }
  304.   if( @board != 9 ){
  305.     die "9 行のデータが必要です\n";
  306.   }
  307. }
  308.  
  309. # ***** メイン *****
  310.  
  311. # 初期化
  312. &init_bit_table();
  313.  
  314. &read_data( shift );
  315.  
  316. # 解析
  317. &analysis();
  318. print "***** 確定サーチ中 *****\n\n";
  319. if( &kakutei_search_1() ){
  320.   &print_board();
  321. } else {
  322.   print "***** 探索中 *****\n\n";
  323. #  &search( 0 );
  324.   &search_1();
  325. }
  326.  
  327. # end of file
  328.